package code1_100.code21_30;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 韩迪
 * @date 2022/03/21 22:07
 **/
public class Code22 {
    public List<String> generateParenthesis(int n) {

        //动态规划求解：问题可描述为    (  +  p  +  )  +  q
        //其中 p + q = i-1;(p,q:括号数)
        List<List<String>> result = new ArrayList<>();
        List<String> list1 = new ArrayList<>();
        list1.add("");
        result.add(list1);
        List<String> list2 = new ArrayList<>();
        list2.add("()");
        result.add(list2);
        //存储括号数为i时的字符串，并将其放入集合，存入result的index下
        for (int i = 2; i <= n; i++) {
            List<String> list = new ArrayList<>();
            // 对p,q的括号个数进行排列组合
            for (int j = 0; j < i; j++) {
                //p为j个括号个数时的括号集合
                List<String> p = result.get(j);//p
                //q为i-1-j个括号个数时的括号集合
                List<String> q = result.get(i-1-j);//q =  i-1-p
                //进行排列组合，即可获取括号数为i的括号组合
                for (String ps:p){
                    for (String qs : q){
                        String str = "(" + ps+ ")" + qs;
                        list.add(str);
                    }
                }
            }
            result.add(list);
        }
        return result.get(n);
    }
}
